import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
//找到字符中的所有异位字符
public class leetcode438 {
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> list=new ArrayList<>();
        int[] hash1=new int[26];
        char[] p=pp.toCharArray();
        for(char x:p){
            hash1[x-97]++;
        }
        int left=0;
        char[] hash2=new char[26];
        char[] s=ss.toCharArray();
        for(int right=0;right<s.length;right++){
            hash2[s[right]-97]++;
            if(right-left+1==p.length){
                int flag=0;
                for(int i=0;i<26;i++){
                    if(hash1[i]!=hash2[i]){
                        flag=-1;
                        break;
                    }
                }
                System.out.println("flag"+flag);
                if(flag==0){
                    list.add(left);
                }
                hash2[s[left]-97]--;
                left++;
            }
        }
        return list;
    }
    public List<Integer> findAnagrams2(String ss, String pp) {
        List<Integer> list=new ArrayList<>();
        char[] s=ss.toCharArray();
        char[] p=pp.toCharArray();
        int[] hash1=new int[26];
        int[] hash2=new int[26];
        for(char x:p) {
            hash1[x-97]++;
        }
        int left=0;
        int count=0;
        int m=p.length;
        for(int right=0;right<s.length;right++){
            char in=s[right];
            hash2[in-97]++;
            if(hash2[in-97]<=hash1[in-97]){
                count++;
            }
            if(right-left+1>m){
                char out=s[left];
                left++;

                if(hash2[out-97]<=hash1[out-97]){
                    count--;
                }
                hash2[out-97]--;
            }
            if(count==m)
                list.add(left);
        }
        return list;
    }

}

